#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
   private:
    int indexOf(vector<int> arr, int ele) {
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] == ele) {
                return i;
            }
        }
        return 0;
    }
    TreeNode* buildLeftAndRight(vector<int>& preorder,
                                int p_start,
                                int p_end,
                                vector<int>& inorder,
                                int i_start,
                                int i_end) {
        if (p_start > p_end || i_start > i_end || preorder.size() == 0 ||
            inorder.size() == 0 || p_start > preorder.size() - 1 ||
            i_start > inorder.size() - 1 || p_end < 0 || i_end < 0) {
            return NULL;
        }
        //根据给定的前序和后序构建二叉树
        int pivot = preorder[p_start];
        TreeNode* root = new TreeNode(pivot);
        int pivot_index = indexOf(inorder, pivot);  // 3
        root->left = buildLeftAndRight(preorder, p_start + 1,
                                       p_start + pivot_index - i_start, inorder,
                                       i_start, pivot_index - 1);
        root->right =
            buildLeftAndRight(preorder, p_start - i_start + pivot_index + 1,
                              p_end, inorder, pivot_index + 1, i_end);
        return root;
    }

   public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildLeftAndRight(preorder, 0, preorder.size() - 1, inorder, 0,
                                 inorder.size() - 1);
    }
};

int main() {
    cout << "Hello, World!";
    vector<int> p;
    vector<int> i;
    // 9,3,15,20,7
    p.push_back(1);
    p.push_back(2);
    p.push_back(3);
    p.push_back(4);
    p.push_back(5);
    p.push_back(6);
    i.push_back(1);
    i.push_back(2);
    i.push_back(3);
    i.push_back(4);
    i.push_back(5);
    i.push_back(6);
    TreeNode* tmp = Solution().buildTree(p, i);
    return 0;
}